#include "binary_tree.h"
#include "constants.h"

typedef struct tagSortArg
{
	pBNode *arr;
	int index;
} SortArg, *pSortArg;

pBTree CreateBTree(CompareFunc func)
{
	pBTree tree = (pBTree)SafeMalloc(sizeof(BTree));
	tree->Compare = func;
	tree->root = NULL;
	tree->nodeCount = 0;
	return tree;
}

pBNode CreateNewNode(void *data)
{
	pBNode node = (pBNode)SafeMalloc(sizeof(BNode));
	node->p = NULL;
	node->left = NULL;
	node->right = NULL;
	node->data = data;
	return node;
}

pBNode InsertBNode(pBTree tree, void *data)
{
	pBNode x, node;
	int compareValue;

	if(tree->root == NULL)
	{
		tree->root = CreateNewNode(data);
		tree->nodeCount = 1;
		return tree->root;
	}
	else
	{
		x = tree->root;
		while(TRUE)
		{
			compareValue = tree->Compare(x->data, data);
			if(compareValue == 0)
				return x;
			else if(compareValue < 0)
			{
				if(x->right != NULL)
					x = x->right;
				else 
				{
					node = CreateNewNode(data);
					x->right = node;
					node->p = x;
					tree->nodeCount++;
					return node;
				}
			}
			else
			{
				if(x->left != NULL)
					x = x->left;
				else
				{
					node = CreateNewNode(data);
					x->left = node;
					node->p = x;
					tree->nodeCount++;
					return node;
				}
			}
		}
	}
}

pBNode SearchBTree(pBTree tree, void *data)
{
	pBNode x;
	int comVal;

	x = tree->root;

	while(x != NULL)
	{
		comVal = tree->Compare(x->data, data);
		if(comVal == 0)
			return x;
		else if(comVal < 0)
			x = x->right;
		else
			x = x->left;
	}

	return NULL;
}

void ReleaseBNode(pBNode node)
{
	if(node != NULL)
	{
		ReleaseBNode(node->left);
		ReleaseBNode(node->right);
		free(node);
	}
}

void ReleaseBTree(pBTree tree)
{
	if(tree != NULL)
		ReleaseBNode(tree->root);

	free(tree);
}

pBNode TraverseNodeDesc(pBNode node, void *data, void (*Action)(pBNode, void *))
{
	if(node != NULL)
	{
		TraverseNodeDesc(node->right, data, Action);
		Action(node, data);
		TraverseNodeDesc(node->left, data, Action);
	}
}

pBNode TraverseNodeAsc(pBNode node, void *data, void (*Action)(pBNode, void *))
{
	if(node != NULL)
	{
		TraverseNodeAsc(node->left, data, Action);
		Action(node, data);
		TraverseNodeAsc(node->right, data, Action);
	}
}

void TraverseBNode(pBNode node, void *data, int desc, void (*Action)(pBNode, void *))
{
	if(desc)
		TraverseNodeDesc(node, data, Action);
	else
		TraverseNodeAsc(node, data, Action);
}

void SortNodeAction(pBNode node, void *data)
{
	pSortArg arg = (pSortArg)data;
	arg->arr[arg->index++] = node;
}

pBNode *SortBTree(pBTree tree, int desc, int *length)
{
	pSortArg arg;
	pBNode *arr;

	if(tree->nodeCount == 0)
	{
		arr = NULL;
		return arr;
	}
	arg = (pSortArg)SafeMalloc(sizeof(SortArg));
	arg->index = 0;
	arr = (pBNode*)SafeMalloc(sizeof(pBNode) * tree->nodeCount);
	arg->arr = arr;
	TraverseBNode(tree->root, arg, desc, SortNodeAction);

	length = &(arg->index);
	free(arg);
	return arr;
}